package com.itheima.leetcode.od.b.dynamicprogramming.bitwise;

import java.util.Arrays;

/**
 * <h3>数字 1 的个数</h3>
 */
public class CountDigitOneLeetcode233 {
    public static void main(String[] args) {
        CountDigitOneLeetcode233 countDigitOne = new CountDigitOneLeetcode233();
        System.out.println(countDigitOne.countDigitOne(13));
    }

    private char[] s;
    private int[][] emeo;  // 备忘录（记忆数列）

    public int countDigitOne(int n) {
        s = Integer.toString(n).toCharArray();
        int m = s.length;
        // 根据题目给出的范围，一个数中 1 的数量最多只有 10 种情况
        emeo = new int[m][10]; // 为什么是 emeo[i][oneCnt] ,这个需要你好好思考一下
        // 初始化为 -1
        for (int i = 0; i < m; i++) {
            Arrays.fill(emeo[i], -1);
        }
        return f(0, 0, true);
    }

    /**
     * 回从第 i 位开始，数字中 1 的个数<br/>
     * 建议参考文档<a href="https://lfool.github.io/LFool-Notes/algorithm/%E6%95%B0%E4%BD%8DDP.html"><b>数位DP</b></a>，但是作者 <b>状态复用</b> 那一块写的有点瑕疵，很容易让人误解
     *
     * @param i
     * @param oneCnt
     * @param isLimit
     * @return
     */
    private int f(int i, int oneCnt, boolean isLimit) {
        // 结束条件：到达此处的路径均为可行解，oneCnt 表示该可行解中 1 的数量
        if (i == s.length) {
            return oneCnt;
        }
        // 「没有限制」且「该状态结果已经计算出」，则直接返回
        if (!isLimit && emeo[i][oneCnt] != -1) { // 重点，第 i 位字符之前计数为 oneCnt 写入 记忆数列
            return emeo[i][oneCnt]; // 记忆数列记录的是 总数，
        }
        int up = isLimit ? s[i] - '0' : 9;
        int res = 0; // res 记录的是计数的和
        for (int d = 0; d <= up; d++) {
            res += f(i + 1, oneCnt + (d == 1 ? 1 : 0), isLimit && d == up);
        }
        // 记录该状态的结果
        if (!isLimit) {
            emeo[i][oneCnt] = res; // 因为 矩阵 里存储的是总数，!isLimit之后的计数可以复用，所以当 oneCnt 相等时场景才是坐标（res = oneCnt + f(i)）
        }
        return res;
    }
}